package com.leetCode.four;

import java.lang.reflect.Method;
import java.util.Arrays;
import java.util.Set;

public class Problem42_2 {

	public static void main(String[] args) throws Exception {
		 Solution s = getInstance();
		 
//		 int[] test = {2,0,2};
//		 int[] test = {5,4,1,2};
		 int[] test = {0,1,0,2,1,0,1,3,2,1,2,1};
		 int[] test2 = new int[50000];
		 for (int i = 0; i < test2.length; i++) {
			 test2[i] = (int) (Math.random()*100000);
		}
		 System.out.println("的mo");
//		 int[] test = {4,2,3};
		 int trap = s.trap(test2);
		 Math.pow(1, 2);
		 
		 System.out.println("最终结果"+trap);
//{3=[7], 2=[3, 8, 10], 1=[1, 4, 6, 9, 11], 0=[0, 2, 5]}

	}
	
	/**
	 * 定位最左边
	 * @author lyk
	 *
	 */
	class Solution {
	    public int trap(int[] height) {
//	    	System.out.println(Arrays.toString(height));
	    	if(height==null || height.length<=1){
	    		return 0;
	    	}
	    	int length = height.length, result = 0;
	    	int left = height[0], right = -1;
	    	boolean findMax = false;
	    	for (int i = 1; i < length; i++) {	    		
	    		if(height[i]>=left){
	    			findMax = true;
	    			result = result + trap(Arrays.copyOfRange(height, i, length));
	    			right = i;
	    			break;
	    		}
			}
	    	
	    	if(!findMax){//右边找不到最大值就减一在处理 		
	    		height[0] = height[0] - 1;
	    		result = result + trap(height);    		
	    	}else{
//	    		System.out.println("需要处理:"+Arrays.toString(Arrays.copyOfRange(height, 0, right+1)));
	    		int[] copyOfRange = Arrays.copyOfRange(height, 0, right+1);
	    		if(copyOfRange.length>2){
	    			int sum = left*(right-1);
		    		for (int i = 1; i < copyOfRange.length-1; i++) {
		    			sum -= copyOfRange[i];
					}
//		    		System.out.println("结果:"+sum);
		    		result += sum;	 
	    		}	    		   		
	    	}
//	    	System.out.println(result);
	    	return result;
	    }
	}
	
	static Solution getInstance() throws Exception{
		String className = Thread.currentThread().getStackTrace()[1].getClassName();
		Class<?> forName = Class.forName(className);
		Method method = forName.getMethod("newS", null);
		Solution solution = (Solution) method.invoke(forName.newInstance(),null);
		return solution;
	}
	
	public Solution newS(){
		return new Solution();
	}
	
}
